package com.wwz.leetcode;

import org.junit.Test;

/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * <p>
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 */
public class LeetCode70 {


    /**
     * f(x)=f(x−1)+f(x−2)   f(0) = 0 ,f(1) = 1 ,f(2)=2，f(3) = 3，f(4) = 5f(4)=5
     *
     * @param n 多少台阶
     * @return
     */
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int p, q = 1, r = 2;
        for (int i = 3; i <= n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }


    @Test
    public void test() {
        System.out.println(climbStairs(44));
    }

    // 递归超时
//    private int count = 0;
//
//    public int climbStairs(int n) {
//        if (n == 0)
//            return count;
//        tryClimb(n);
//        return count;
//    }
//
//    private void tryClimb(int n) {
//        if (n == 0) {
//            count++;
//        }
//        if (n < 0) {
//            return;
//        }
//        tryClimb(n - 1);
//        tryClimb(n - 2);
//
//    }
}
